import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @ClassName Offer54
 * @Description 剑指 Offer 54. 二叉搜索树的第k大节点
 * @Author clockTown
 * @Date 2021/8/28 10:32
 * @Version 1.0
 */
class Offer54 {
}

class Offer54V0 {
    PriorityQueue<TreeNode> queue = new PriorityQueue<>((o1, o2) -> (o2.val - o1.val));

    public int kthLargest(TreeNode root, int k) {
        dfs(root);
        while (!queue.isEmpty() && k >= 0) {

            queue.poll();
            k--;
        }
        return queue.isEmpty() ? -1 : queue.poll().val;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        queue.offer(root);
        dfs(root.right);
    }
}


class Offer54V1 {
    List<TreeNode> list = new LinkedList<>();

    public int kthLargest(TreeNode root, int k) {
        if (root == null) {
            return -1;
        }
        dfs(root);

        return list.size() - k >= 0 ? list.get(list.size() - k).val : -1;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        list.add(root);
        dfs(root.right);
    }
}


class Offer54V2 {
    /**
     * 形参k不能随着dfs的迭代而不断变化，为了记录迭代进程和结果，引入类变量count和res。
     */
    int count=0, res=0;
    public int kthLargest(TreeNode root, int k) {
        //利用形参值k对类变量count进行初始化
        this.count=k;
        //这里不要引入形参k，dfs中直接使用的是初始值为k的类变量count
        dfs(root);
        return res;
    }
    public void dfs(TreeNode root){
        //当root为空或者已经找到了res时，直接返回
        if(root==null||count==0) {
            return;
        }
        dfs(root.right);
        //先--，再判断
        if(--count==0){
            res = root.val;
            //这里的return可以避免之后的无效迭代dfs(root.left);
            return;
        }
        dfs(root.left);
    }
}